package algoritmo;

import java.awt.Point;
import java.util.LinkedList;
import java.util.ListIterator;

/**
 * TODO:
 * * Verificar se cheiros funcionam
 * * Estimar posição de ladrões cheirados
 *
 * * Estamos sujeitos a emboscadas. Se ladrao está fora do campo de visão, mas dentro da área de ameaça
 *  (ex. ladrao está atrás de um mudo, não podemos vê-lo, mas logo que passarmos pelo muro ele nos verá e não teremos
 *  chance de fugir - imagine ele atrás da porta e a gente entrando no quarto).
 *  
 *  
 *  * Implementar classes de comportamentos com prioridades
 *  * Guardar moedas no banco quando ficar rico
 *  * Implementar pathfinding para ladrão - fazer caminho mais curto que o ladrão possa para nos pegar
 *     considerando q ele nao pode pegar moedas ou pastilhas, isso pode ajudar em alguns casos evitando
 *     fugir por besteira
 *     
 *     
 *  PROBLEMAS:
 *  
 *  PROBLEMA MUITO GRANDE::: as vezes o pathfind troca o caminho com a variação de personagens móveis, o que faz com que
 *  	o bixo entre em loop (nao em codigo, mas no jogo, fique andando nas mesmas posicoes), em geral isso acontece porque
 *  	o outro bixo já está em loop!!!!
 *  
 *  	O problema acima se dá em vários casos. Um deles é quando queremos ir para o desconhecido mais proximo. Pegamos o mais proximo
 *  	pela dist de manhattan, sem considerar barreiras, contudo esse ponto na verdade, devido às barreiras, pode demorar mais para chegarmos
 *  	entao enquanto nos movemos para ir para tal ponto, acabamos nos aproximando de outro ponto desconhecido que agora tem a menor dist de manhattan
 *  	a partir dai, trocamos o destino e num caso ruim, ficando alternando entre tais pontos.
 *   
 *   - qndo nao tiver o q fazer vá para local com maior área livre (menor número de paredes)
 *     dividir mapa em regioes e calcular densidade de paredes, ir para aquela regiao com menor densisdade
 *     
 * COMPLETE:
 * 
 * * Comportamentos:
 * 	* Guardar no banco qndo interessante
 *  * Pegar / evitar pegar pipula qndo interessante
 *  * Fugir ladr�o
 *  * Descobrir mundo
 *  * Descobrir mundo e moedas e banco
 *  * Melhor roda para pegar moedas
 *  
 * PARTIAL:
 * 
 * 
 * IGNORED:
 *  * Banco mais proximo deve considerar densidade de ladrões próximos a ele (acho q nao vai ter mais q um banco)
 * 
 * 
 */

public class Poupador extends ProgramaPoupador 
{
	// armazena estados conhecidos do mundo --- linha -> y; coluna -> x;
	private int[][] mundo;
	
	/**
	 * Mundo de cheiros possui o tamanho suficiente para manter cheiros mais fracos (mais o meu quadro)
	 */
	private int[][] cheiro;
	private int tick; // tick atual
	private LinkedList<Point> ultimasPosicoes;
	private LinkedList<Point> bancos;
	private LinkedList<Lembranca> ladroes;
	private LinkedList<Lembranca> poupadores;
	private LinkedList<Lembranca> locaisInatingiveis;
	private Point pontoDesconhecidoProximo;	
	
	/**
	 * Tempo que vamos dedicar para fugir de loops;
	 */
	private int tempoEvitandoLoop;
	private Point destinoEvitarLoop;
	
	/**
	 * Nao use essa variavel direitamente. Se vc quer o nro total de jogadas imunes, utilize getNumeroJogasImunes().
	 * Essa variavel representa o nro de jogadas que podemos desprezar a fuga (para evitar loops)
	 */
	private int numeroJogadasImunesInternas;
	
	public int getNumeroJogasImunes()
	{
		return sensor.getNumeroJogadasImunes() + numeroJogadasImunesInternas;
	}
	
	public Poupador()
	{		
		super();	
		inicializaMundo();
		
		ultimasPosicoes = new LinkedList<Point>();
		bancos =  new LinkedList<Point>();
		locaisInatingiveis = new LinkedList<Lembranca>();
		ladroes = new LinkedList<Lembranca>();
		poupadores = new LinkedList<Lembranca>();
		pontoDesconhecidoProximo = null;
		numeroJogadasImunesInternas = 0;
		tempoEvitandoLoop = 0;
		tick = 0;
		
		destinoEvitarLoop = null;
	}
	
	// retorna posicao de forma segura
	private Point getPos()
	{
		return (Point)sensor.getPosicao();
	}
	
	private void lembraLadrao()
	{
		lembra(ladroes, Constantes.LEMBRANCA_LIMITE_LADRAO, Constantes.VISAO_VAZIO);
	}
	
	private void lembraPoupador()
	{
		lembra(poupadores, Constantes.LEMBRANCA_LIMITE_POUPADOR, Constantes.VISAO_VAZIO);
	}		
	
	/**
	 * Esquece que alguns locais eram inatingiveis com o passar do tempo
	 * Isso faz que com voltemos lá para tentar acessá-los novamente. Pode ser q um ladrão ficou no meio do caminho
	 * e não quis deixar a gente entrar no local.
	 */
	private void lembrarLocalInatingivel()
	{
		lembra(locaisInatingiveis, Constantes.LEMBRANCA_LIMITE_INATINGIVEL, Constantes.VISAO_DESCONHECIDO);
	}
	
	private void lembra(LinkedList<Lembranca> lista, int tempoLimite, int valorLembrancaApagada)
	{
		ListIterator<Lembranca> list = lista.listIterator();
		Lembranca l;
		
		while (list.hasNext())
		{		
			l = list.next();
			
			// vimos a lembranca ha mto tempo, tire-a da lista
			if (++l.tempo > tempoLimite)
			{
				list.remove();
				
				// temos que apagar o mundo também
				apagaLembranca(l, valorLembrancaApagada);
			}
		}
	}
	
	private void ignorarLocalInatingivel(Point localInatingivel)
	{		
		// atualiza mundo
		mundo[localInatingivel.y][localInatingivel.x] = Constantes.VISAO_INATINGIVEL;
		locaisInatingiveis.add(new Lembranca(localInatingivel, Constantes.VISAO_INATINGIVEL));
	}
	
	private void novoPoupador(Point pos, int valor)
	{
		novaLembranca(pos, valor, poupadores);
	}
	
	private void novoLadrao(Point pos, int valor)
	{
		novaLembranca(pos, valor, ladroes);
	}		
	
	private void apagaLembranca(Lembranca l, int novoValor)
	{
		// temos que apagar a lembranca do mundo
		if (mundo[l.posicao.y][l.posicao.x] == l.valor)
			mundo[l.posicao.y][l.posicao.x] = novoValor;		
	}
	
	private void novaLembranca(Point pos, int valor, LinkedList<Lembranca> lista)
	{
		boolean atualizado = false;
		// se vimos uma lembranca, atualizamos tal lembranca na nossa lista		
		for (Lembranca l : lista)
		{
			if (l.valor == valor)
			{
				// apaga lembranca antiga do mundo
				apagaLembranca(l, Constantes.VISAO_VAZIO);
				l.posicao.setLocation(pos);
				l.tempo = 0;
				atualizado = true;
				break;
			}
		}
		
		if (!atualizado)
		{
			// se nao encontramos lembranca na lista, adicionamos nova
			lista.add(new Lembranca(pos, valor));
		}
	}
	
	/**
	 * Retorna posicao de ladrao mais proximo conhecido.
	 * Retorna NULL se nao sabemos onde estao os ladroes
	 * @param pos
	 * @param distancia retorna distancia do ladrao proximo
	 * @return
	 */
	public Point ladraoMaisProximo(Point pos, Holder<Integer> distancia)
	{
		int dist;
		int minDist;
		Point minPos;
		
		minDist = Integer.MAX_VALUE;
		minPos = new Point();
		
		for (Lembranca l : ladroes)
		{
			dist = Constantes.manhattan(l.posicao, pos);
			
			if (dist < minDist)
			{
				minDist = dist;
				minPos.setLocation(l.posicao);
			}
		} 
		
		distancia.value = minDist;
		
		if (minDist == Integer.MAX_VALUE)
			return null;
		
		return minPos;
	}
	
	// inicializa mundo em estado desconhecido
	private void inicializaMundo()
	{
		mundo = new int[Constantes.MUNDO_TAM][Constantes.MUNDO_TAM];
		// precisamos lembrar dos cheiros proximos, pq eles somem depois de qualquer forma
		cheiro = new int[Constantes.CHEIRO_TAMLEMBRANCA][Constantes.CHEIRO_TAMLEMBRANCA];
				
		
		for (int i = 0; i < Constantes.MUNDO_TAM; i++)
			for (int j = 0; j < Constantes.MUNDO_TAM; j++)
				mundo[i][j] = Constantes.VISAO_DESCONHECIDO;				

		for (int i = 0; i < Constantes.CHEIRO_TAMLEMBRANCA; i++)
			for (int j = 0; j < Constantes.CHEIRO_TAMLEMBRANCA; j++)
				cheiro[i][j] = Constantes.CHEIRO_SEMCHEIRO;
	}

	// descobre novas areas e atualiza informações antigas
	private void descobreMundo()
	{
		Point pos = getPos();
		int[] visao = sensor.getVisaoIdentificacao();
		int[] cheiroLadrao = sensor.getAmbienteOlfatoLadrao();
		int x, y;
		
		// atualiza tick atual
		tick++;
		
		// atualiza jogadas internas
		if (numeroJogadasImunesInternas > 0)
			numeroJogadasImunesInternas--;
		
		if (tempoEvitandoLoop > 0)
		{
			tempoEvitandoLoop--;
		}
		else
		{		
			// aqui tempoEvitandoLoop == 0
			destinoEvitarLoop = null;	
		}
		
		x = pos.x;
		y = pos.y;
				
		
		// lembramos de ladroes vistos
		lembraLadrao();
		lembraPoupador();
		lembrarLocalInatingivel();
		
		// onde estamos está vazio (na verdade, estará qndo sairmos daqui)
		mundo[y][x] = Constantes.VISAO_VAZIO;
		
		// atualiza mundo visto
		for (int i = 0; i < visao.length; i++)
		{
			if (i == 0 || i == 5 || i == 10 || i == 14 || i == 19)
			{
				x = pos.x - 2;
				y = pos.y;
				
				if (i == 0)
					y -= 2;
				else if (i == 5)
					y -= 1;
				else if (i == 14)
					y += 1;
				else if (i == 19)
					y += 2;
			}
			
			// soh vamos atualizar algo se nao estivermos na posicao do personagem
			if (y != pos.y || x != pos.x)
			{
				// se estivermos olhando para fora dos limites do mundo, apenas prossiga sem fazer nada, nao existe nada lá fora
				if (y > -1 && y < Constantes.MUNDO_TAM && x > -1 && x < Constantes.MUNDO_TAM)
				{
					// apenas atualizamos o que podemos ver
					if (visao[i] != Constantes.VISAO_SEMVISAO)
					{
						mundo[y][x] = visao[i];
						
						switch(visao[i])
						{				
							// guarda bancos descobertos
							case Constantes.VISAO_BANCO:
								novoBanco(new Point(x, y));
								break;
								
							default:
								// lembra de ladroes
								if (Constantes.contemLadrao(visao[i]))
									novoLadrao(new Point(x, y), visao[i]);
								else if (Constantes.contemPupador(visao[i]))
									novoPoupador(new Point(x, y), visao[i]);
								break;
						}
							
						
					}
				}
			}
			else
			{
				// queremos apenas pular posicao x,y nao o valor em i da visao
				i--;
			}
			
			x++;
		}
		
		// agora que acabamos de atualizar mundo visto
		// eh possivel que ladroes tenham se escondido e por isso nao atulizamos eles
		// vamos procuprar por ladroes q nao estao mais lá e sumir com eles
		// TODO: apagar ladroes "invisiveis"
		// Nao sei se vale a pena, talvez apenas reduzir o tempo de lembrança, nao sei o qual bom isso pode fazer
		
		// em qual quadro de cheiro estamos
		int centroCheiro = Constantes.CHEIRO_TAMLEMBRANCA / 2;
		Point posAnterior = getPosicaoAnterior();
		Point minhaPos = getPos();
		Point variacaoPosicao = new Point(minhaPos.x - posAnterior.x, minhaPos.y - posAnterior.y);
		Point cheiroOrigem, cheiroDestino;
		
		cheiroDestino = new Point();
		cheiroOrigem = new Point();
		
		// se fomos para esquerda
		if (variacaoPosicao.x < 0)
		{
			// copiamos o da direita para o nosso
			cheiroDestino.x = 0;
			cheiroOrigem.x = 1;
		}
		// se fomos p/ direita
		else if (variacaoPosicao.x > 0)
		{
			// copiamos o nosso para o da direita
			cheiroDestino.x = 1;
			cheiroOrigem.x = 0;
		}
		else
		{
			// se nao andamos, nao fazemos nada pois podemos ter q mexer em y
		}	
		
		// se fomos para cima
		if (variacaoPosicao.y < 0)
		{
			// copiamos o de baixo para o nosso
			cheiroDestino.y = 0;
			cheiroOrigem.y = 1;
		}
		// se fomos p/ baixo
		else if (variacaoPosicao.y > 0)
		{
			// copiamos o nosso para o de baixo
			cheiroDestino.y = 1;
			cheiroOrigem.y = 0;
		}
		else
		{
			// se nao andamos, nao fazemos nada
		}
		
		// atualiza mundo cheirado
		// a cada frame, precisamos transladar cheiros se andamos
		// e atualizar cheiros na nossa regi�o cheirada
		// e atualizar "data" dos cheiros
		for (x = 0; x < Constantes.CHEIRO_TAMLEMBRANCA; x++)
		{		
			for (y = 0; y < Constantes.CHEIRO_TAMLEMBRANCA; y++)
			{
				// soh translada cheiros se estivemos nos limites adequados
				if (x < Constantes.CHEIRO_TAMLEMBRANCA - 1 && y < Constantes.CHEIRO_TAMLEMBRANCA - 1)
					cheiro[y + cheiroDestino.y][x + cheiroDestino.x] = cheiro[y + cheiroOrigem.y][x + cheiroOrigem.x]; 
				
				// se ha cheiro no quadro
				if (cheiro[y][x] > 0)
				{
					// se o cheiro eh mto antigo, esquechemos
					if (cheiro[y][x] == Constantes.CHEIRO_CHEIROLIMITE)
						cheiro[y][x] = Constantes.CHEIRO_SEMCHEIRO;
					else // senao atualizamos quanto tempo ele tem
						cheiro[y][x]++;
				}
			}
		}
		
		// atualiza cheiros da regiao cheirada
		cheiro[centroCheiro - 1][centroCheiro - 1] = cheiroLadrao[0];
		cheiro[centroCheiro - 1][centroCheiro    ] = cheiroLadrao[1];
		cheiro[centroCheiro - 1][centroCheiro + 1] = cheiroLadrao[2];
		cheiro[centroCheiro    ][centroCheiro - 1] = cheiroLadrao[3];
//		cheiro[centroCheiro    ][centroCheiro    ] = cheiroLadrao[ESTA SERIA MINHA POSICAO CENTRAL];
		cheiro[centroCheiro    ][centroCheiro + 1] = cheiroLadrao[4];
		cheiro[centroCheiro + 1][centroCheiro - 1] = cheiroLadrao[5];
		cheiro[centroCheiro + 1][centroCheiro    ] = cheiroLadrao[6];
		cheiro[centroCheiro + 1][centroCheiro + 1] = cheiroLadrao[7];
	}

	/**
	 * Retorna qual o ponto desconhecido mais próximo.
	 * Retorna NULL quando não existir ponto desconhecido.
	 * @return
	 */
	public Point desconhecidoMaisProximo()
	{
		if (pontoDesconhecidoProximo != null)
		{
			// se jah sabemos alguns ponto desconhecido proximo, entao vemos se ele ainda eh desconhecido
			if (mundo[pontoDesconhecidoProximo.y][pontoDesconhecidoProximo.x] != Constantes.VISAO_DESCONHECIDO)
			{
				// se nao for mais desconhecido, entao nao conhecemos o ponto!
				pontoDesconhecidoProximo = null;
			}			
		}
		
		if (pontoDesconhecidoProximo == null)
			pontoDesconhecidoProximo = coisaMaisProximo(Constantes.VISAO_DESCONHECIDO);
		
		if (pontoDesconhecidoProximo == null)
		{
			// de fato nao ha pontos desconhecidos mais
			return null;
		}
		
		// retorna uma copia para nao mancharem a nossa variavel
		return new Point(pontoDesconhecidoProximo);
	}
	
	public Point moedaMaisProxima()
	{
		return coisaMaisProximo(Constantes.VISAO_MOEDA);
	}
	
	public Point coisaMaisProximo(int valorCoisa)
	{
		int minDist;
		int dist;
		Point curPoint;
		Point minPoint;
		Point pos;
		
		pos = getPos();
	
		minDist = Integer.MAX_VALUE;
		curPoint = new Point();
		minPoint = new Point();

		/*
		 * TODO: Otimizar busca.
		 * Pontos mais proximos estarao em X,Y mais proximos de POS 
		 */
		for (int i = 0; i < Constantes.MUNDO_TAM; i++)
		{
			for (int j = 0; j < Constantes.MUNDO_TAM; j++)
			{
				if (mundo[j][i] == valorCoisa)
				{
					curPoint.setLocation(i, j);
					dist = Constantes.manhattan(pos, curPoint);
					
					if (dist < minDist)
					{
						minPoint.setLocation(curPoint);
						minDist = dist;
					}
				}
			}
		}

		// se nao encontramos nenhum ponto desconhecido, retorne null
		if (minDist == Integer.MAX_VALUE)
			return null;
				
		return minPoint;
	}
	
	/* lembra de banco visto */
	private void novoBanco(Point posBanco)
	{
		for (Point b : bancos)
		{
			// se conhece banco, nao o adiciona na lista
			if (b.x == posBanco.x && b.y == posBanco.y)
				return;
		}
		
		bancos.add(posBanco);
	}
	
	/*
	 * Retorna posicao do banco mais proximo ou NULL se nao conhece nenhum banco
	 */
	public Point bancoMaisProximo()
	{
		int dist, min;
		
		Point pos = getPos();
		Point posBanco = null;
		min = Integer.MAX_VALUE;
		
		for (Point b : bancos)
		{
			// isso acontecerá qndo o banco estiver inacessivel
			if (mundo[b.y][b.x] == Constantes.VISAO_INATINGIVEL)
				continue; // se nao podemos usar o banco, vamos para outro banco (se houver)
			
			dist = Constantes.manhattan(b, pos);

			// se encontramos distancia menor que a menor conhecida, atualizamos os dados
			if (dist < min)
			{
				min = dist;
				posBanco = b;
			}
		}
		
		return posBanco;
	}

	/**
	 * Retorna algum local do mundo que seja distante do banco e de preferencia q nao seja um local que impeça a passagem de
	 * outros.
	 * @return
	 */
	private Point localErmo()
	{
		Point p = new Point();
		Point banco = bancoMaisProximo();		
		
		// busca no perimetro do mundo locais distantes do banco e validos
		for (int i = 0; i < Constantes.MUNDO_TAM; i++)
		{
			p.y = 0;
			p.x = i;			
			
			if (Constantes.isValidPoint(p, 0, mundo) && (banco == null || Constantes.manhattan(p, banco) > 3))
				return p;
			
			p.y = Constantes.MUNDO_TAM-1;
			p.x = i;
			
			if (Constantes.isValidPoint(p, 0, mundo) && (banco == null || Constantes.manhattan(p, banco) > 3))
				return p;
			
			p.y = i;
			p.x = 0;			
			
			if (Constantes.isValidPoint(p, 0, mundo) && (banco == null || Constantes.manhattan(p, banco) > 3))
				return p;
			
			p.y = i;
			p.x = Constantes.MUNDO_TAM-1;
			
			if (Constantes.isValidPoint(p, 0, mundo) && (banco == null || Constantes.manhattan(p, banco) > 3))
				return p;
		}		
		
		return null;
	}
	
	/**
	 * Verifica se estamos nos movendo em loop.
	 * @return número de loops realizados. 0 se não há loops
	 */
	private int historicoLoop()
	{
		Point[] hist;
		int loopStart;
		int loopNext;
		int loopCount;
		int loopLen;
		
		if (ultimasPosicoes.size() == 0)
			return 0;
		
		hist = ultimasPosicoes.toArray(new Point[0]);
		
		loopStart = 0;
		loopNext = 0;
		loopCount = 0;
		
		// buscamos loop inicial
		for (int i = 1; i < hist.length; i++)
		{
			// loop se inicia em loopStart e vai ateh alguma posicao que seja igual ao inicio
			if (hist[i].equals(hist[loopStart]))
			{
				loopNext = i;
				break;
			}
		}
		// nao incrementamos loopCount pois voltar a posicao inicial apenas nao significa que estamos em loop necessariamente
		
		loopLen = loopNext - loopStart;
		
		// se o final do loop nao foi alterado, entao nao ha loop
		// nao queremos loop parados no lugar, entao tamanho do loop tem que ser maior que 1
		if (loopLen < 2)
			return 0;
		
		// contamos proximos loops, comecando no proximo (possivel) loop
		for (int i = loopNext; i < hist.length; i++)
		{
			if (hist[i].equals(hist[loopStart + (i - loopNext)]))
			{
				// se chegamos ao final do loop
				if (i - loopNext == loopLen - 1)
				{
					// passamos para proximo (possivel) loop
					loopNext = i + 1;
					// incrementamos contagem
					loopCount++;
				}
			}
			else
				// houve uma quebra do loop, nao ha mais loop daqui pra frente
				break; // nao conseguimos formar o loop, podemos parar com o que temos
		}
		
		
		return loopCount;
	}
	
	// guarda caminho dos ultimos quadros andados
	private void historicoPosicoes()
	{
		Point pos = getPos();

		// lembramos um numero limite de ultimas posicoes
		if (ultimasPosicoes.size() == Constantes.HISTORICO_POSICAO_LEN)
			ultimasPosicoes.removeLast();
		
		ultimasPosicoes.addFirst(pos);
	}
	
	// obtem posicao que estavamos no tick anterior
	private Point getPosicaoAnterior()
	{
		if (ultimasPosicoes.size() == 0)
			return getPos();
		
		return ultimasPosicoes.getFirst();
	}	
	
	/**
	 * Retorna algum vizinho de p que seja v�lido.
	 * Se p � valido, retorna p.
	 * Retorna NULL se nao houver nenhum.
	 * @param p
	 * @return
	 */
	private Point obterVizinhoValido(Point p)
	{
		if (p == null)
			return null;
		
		Point v = (Point)p.clone();
		int numeroMoedas = sensor.getNumeroDeMoedas();	
		
		if (Constantes.isValidPoint(v, numeroMoedas, mundo))
			return v;
		
		// cima
		v.y--;
		if (Constantes.isValidPoint(v, numeroMoedas, mundo))
			return v;
		
		// baixo
		v.y += 2;
		if (Constantes.isValidPoint(v, numeroMoedas,  mundo))
			return v;
		
		// esq
		v.y = p.y;
		v.x--;
		if (Constantes.isValidPoint(v, numeroMoedas,  mundo))
			return v;
		
		// dir		
		v.x += 2;
		if (Constantes.isValidPoint(v, numeroMoedas,  mundo))
			return v;

		return null;
	}
	
	/**
	 * Retorna acao a ser tomada para ir da posicao atual ao destino usando pathfinding.
	 * @param posicaoAtual
	 * @param destino
	 * @return
	 */
	private int goTo(Point posicaoAtual, Point destino)
	{
		int acao = Constantes.PARADO;
		Point destinoValido;
		// evita escolher um ponto invalido do mapa
		destinoValido = obterVizinhoValido(destino);

		// soh busque caminhos para destinos validos
		if (destinoValido != null)
		{
			Holder<Integer> ladraoDistancia = new Holder<Integer>(0);
			Point ladrao = ladraoMaisProximo(destinoValido, ladraoDistancia);
			
			// apenas vamos tentar ir para algum lugar que seja seguramente longe do ladrao
			if (ladrao == null || ladraoDistancia.value >= Constantes.MIN_DIST_LADRAO)			
				acao = PathFinding.tomarMelhorDecisao(this, mundo, posicaoAtual, destinoValido);							
		}
		
		// se pathfinding nao encontrou caminho
		// entao o local eh inacessivel
		if (acao == Constantes.PARADO)
		{
			ignorarLocalInatingivel(destino);				
		}
		
		return acao;
	}
	
	// retorna a quanto tempo atrás a posicao foi visitada limitada por no maximo 'tempo' ticks
	// 0 significa que a posicao nao foi visitada, qualquer outro valor indica a quanto tempo isso a visita se deu
	private int isPosicaoRecente(Point pos, int tempo)
	{
		Point p;
		int j = 0;
		
		for (int i = ultimasPosicoes.size() - 1; j < tempo && i >= 0; i--)
		{
			p = ultimasPosicoes.get(i);
			
			if (p.x == pos.x && p.y == pos.y)
				return j + 1;
			
			j++;
		}
		
		return 0;
	}
		
	/*
	 * Olha uma célula e retorna true se ela é valida para movimento (i.e., se podemos nos mover para ela)
	 * distanciaOrigemBusca representa a distancia de manhattan entre a origem da busca e a posicao analisada
	 * Retorna o valor de quão boa ela é em valorRet
	 */
	private boolean olharCelula(Point pos, int distanciaOrigemBusca, Holder<Double> valorRet)
	{
		double valor;
		int valorCelula;
		boolean valida;
		int posRecente;
		int numeroMoedas;
		int numeroJogadasImune;
		
		numeroMoedas = sensor.getNumeroDeMoedas();
		// calcula qual será a quantidade de jogadas imunes q teremos		
		numeroJogadasImune = Math.min(0, getNumeroJogasImunes() - distanciaOrigemBusca);
		
		Point posicaoAtual = getPos();
		Holder<Integer> distanciaLadrao = new Holder<Integer>(0);
		Point ladrao = ladraoMaisProximo(pos, distanciaLadrao);

		valorCelula = mundo[pos.y][pos.x];
		valida = Constantes.isValidPoint(pos, numeroMoedas, mundo);
		valor = 0;
		
		switch(valorCelula)
		{
			case Constantes.VISAO_MOEDA:
				valor = 10d / distanciaOrigemBusca;
				break;

			case Constantes.VISAO_PAREDE:
			case Constantes.VISAO_EXTERNO:			
				valida = false;
				break;
				
			case Constantes.VISAO_BANCO:
				valor = numeroMoedas / (double)distanciaOrigemBusca; // ir ao banco soh se tivermos muitas moedas e por um caminho q nos deixe cada vez mais proximos
				valida = numeroMoedas > 0; // precisamos "entrar no banco" apenas se tivermos moedas
				break;
				
			case Constantes.VISAO_PASTILHA:
				// nao gostamos de pastilhas pq elas sao caras
				// soh pegaremos ela se ela for inicialmente valida
				// e se tiver algum ladrao suficientemente proximo para nos causar problemas
				valida = valida && ( ladrao != null && distanciaLadrao.value < 4 );
				if (valida)
					valor = (3d - numeroJogadasImune) / distanciaLadrao.value; // considera nro de jogadas imune para evitar pegar pastilhas se jah estiver imune
				break;
				
			case Constantes.VISAO_DESCONHECIDO:
				valor = 1d / distanciaOrigemBusca; // interesse pelo desconhecido mais proximo
				break;
				
			default:
				if (Constantes.contemPupador(valorCelula))
				{
					valor = -Constantes.BUSCA_PROFUNDIDADE / (double)distanciaOrigemBusca; // evitamos ficar perto de outros poupadores
					valida = false;
				}

				break;
		}

		int diffMovimento;
		// aqui evitamos caminhos com ladroes proximos se tivermos moedas
		// se estamos considerando a celula do banco, vamos depositar, nao fugir!
		if (ladrao != null && numeroMoedas > 0 && numeroJogadasImune > 0 &&
				(diffMovimento =  distanciaOrigemBusca - distanciaLadrao.value) > -Constantes.MIN_DIST_LADRAO &&
				valorCelula != Constantes.VISAO_BANCO)
		{
			
			// nao eh uma posicao boa, ir para lá significa ser roubado!
			valor = -100 * (Constantes.MIN_DIST_LADRAO + diffMovimento);
			valida = false;
		}
		
		// se o local analisado for invalido (nao podemos nos mover para lá)
		if (!valida)
		{
			// adicionamos uma pequena valoração negativa para evitar que nosso agente durante fugas
			// se aprocime de locais com pouca mobilidade
			valor += - 0.5d / distanciaOrigemBusca;		
		}
		
		valorRet.value = valor;
		
		return valida;
	}
	
	private Acao avaliarMovimento(Point pos, int profundidade, int acaoAnterior, Holder<Double> valorRet)
	{
		return avaliarMovimento(pos, profundidade, acaoAnterior, valorRet, false);
	}
	/*
	 * Avalia movimento até uma certa profundidade e retorna acao escolhida
	 */
	private Acao avaliarMovimento(Point pos, int profundidade, int acaoAnterior, Holder<Double> valorRet, boolean raiz)
	{
		Point _pos;
		Acao minhaDecisao;
		int distManhBusca;
		boolean valido;
		double meuValor;
		
		meuValor = valorRet.value; // guardamos valor até aqui
		_pos = (Point)pos.clone(); // evitamos sujar variavel do chamador
		
		distManhBusca = Constantes.BUSCA_PROFUNDIDADE - profundidade + 1;
		
		// criamos decisao inicial como ficar parado
		minhaDecisao = new Acao(Constantes.PARADO, meuValor, true);

		if (raiz)
		{
			// se somos a raiz, nao temos valor anterior
			meuValor = 0d;
		}
		
		////// BAIXO ///////
		
		if (acaoAnterior != Constantes.CIMA && pos.y < Constantes.MUNDO_TAM - 1)
		{
			_pos.y = pos.y + 1;
			_pos.x = pos.x;
			valido = olharCelula(_pos, distManhBusca, valorRet);		
					
			// se podemos ir para o quadro, entao consideramos ele para analise
			if (valido)
		    {
				// o valor do quadro analisado eh o meu valor mais o valor do proprio quadro
				valorRet.value += meuValor;
				
				// se precisamos analisar maior profundidade, fazemos isso aqui
				if (profundidade > 0)
					avaliarMovimento(_pos, profundidade - 1, Constantes.BAIXO, valorRet);
					
				// decidimos o que vale mais a pena fazer
				if (minhaDecisao.valor < valorRet.value)
				{
					minhaDecisao.acao = Constantes.BAIXO;
					minhaDecisao.valor = valorRet.value;
				}
		    }
		}
		
		//// FIM BAIXO ///////
		
		////// CIMA ///////
		
		if (acaoAnterior != Constantes.BAIXO && pos.y > 0)
		{
			_pos.y = pos.y - 1;
			_pos.x = pos.x;
			
			valido = olharCelula(_pos, distManhBusca, valorRet);
			
			// se podemos ir para o quadro, entao consideramos ele para analise
			if (valido)
		    {			
				// o valor do quadro analisado eh o meu valor mais o valor do proprio quadro
				valorRet.value += meuValor;
				
				// se precisamos analisar maior profundidade, fazemos isso aqui
				if (profundidade > 0)
					avaliarMovimento(_pos, profundidade - 1, Constantes.CIMA, valorRet);
					
				// decidimos o que vale mais a pena fazer
				if (minhaDecisao.valor < valorRet.value)
				{
					minhaDecisao.acao = Constantes.CIMA;
					minhaDecisao.valor = valorRet.value;
				}
		    }
		}
		
		//// FIM CIMA ///////
		

		////// ESQUERDA ///////
		
		if (acaoAnterior != Constantes.DIREITA && pos.x > 0)
		{
			_pos.y = pos.y;
			_pos.x = pos.x - 1;
			
			valido = olharCelula(_pos, distManhBusca, valorRet);
			
			// se podemos ir para o quadro, entao consideramos ele para analise
			if (valido)
		    {			
				// o valor do quadro analisado eh o meu valor mais o valor do proprio quadro
				valorRet.value += meuValor;
	
				// se precisamos analisar maior profundidade, fazemos isso aqui
				if (profundidade > 0)
					avaliarMovimento(_pos, profundidade - 1, Constantes.ESQUERDA, valorRet);
					
				// decidimos o que vale mais a pena fazer
				if (minhaDecisao.valor < valorRet.value)
				{
					minhaDecisao.acao = Constantes.ESQUERDA;
					minhaDecisao.valor = valorRet.value;
				}
		    }
		}
		//// FIM ESQUERDA ///////		

		////// DIREITA ///////
		
		if (acaoAnterior != Constantes.ESQUERDA && pos.x < Constantes.MUNDO_TAM - 1)
		{
			_pos.x = pos.x + 1;
			_pos.y = pos.y;
			
			valido = olharCelula(_pos, distManhBusca, valorRet);
			
			// se podemos ir para o quadro, entao consideramos ele para analise
			if (valido)
		    {			
				// o valor do quadro analisado eh o meu valor mais o valor do proprio quadro
				valorRet.value += meuValor;
	
				// se precisamos analisar maior profundidade, fazemos isso aqui
				if (profundidade > 0)
					avaliarMovimento(_pos, profundidade - 1, Constantes.DIREITA, valorRet);
					
				// decidimos o que vale mais a pena fazer
				if (minhaDecisao.valor < valorRet.value)
				{
					minhaDecisao.acao = Constantes.DIREITA;
					minhaDecisao.valor = valorRet.value;
				}
		    }
		}
		//// FIM DIREITA ///////
		
		// deixamos no valor de retorno o valor da nossa decisao
		valorRet.value = minhaDecisao.valor;
		
		return minhaDecisao;
	}
	
	/**
	 * Decisao a ser tomada antes de executar árvore
	 * @param pos
	 * @param decisao
	 * @return
	 */
	private Acao preDecisao(Point pos)
	{
		// aqui tomamos decisoes baseadas no estado atual
		// se decidirmos ao aqui, a árvore não será olhada

		// por padrao, ficaremos parados (nao tomaremos decisao)
		Acao decisao = new Acao(Constantes.PARADO, 0d, true);
		int numeroMoedas = sensor.getNumeroDeMoedas();
		int numeroJogadasImunes = getNumeroJogasImunes();
		int tamanhoLoop = historicoLoop();
		Point destino;
		boolean bancoConhecido = true;

		// queremos evitar loops se formos encurralados pelos ladroes
		// nestes casos acabaremos em loop dependendo da acao do ladrao
		// se estamos em loop ha tempo suficiente
		if (tamanhoLoop >= Constantes.HISTORICO_LOOP_MAX || tempoEvitandoLoop > 0)
		{
			// etamos tratando loop
			
			// muda totalmente o comportamento para tentar evitar o loop			
			// primeira vez q vamos evitar loop
			if (destinoEvitarLoop == null)
			{
				// TODO: melhorar isso
				// pode ser que escolhamos um ponto que nao tem regiao valida em volta
				destinoEvitarLoop = new Point((int)(Math.random() * (Constantes.MUNDO_TAM-1)),(int)(Math.random() * (Constantes.MUNDO_TAM-1)));
				
				// tempo para evitar loop
				tempoEvitandoLoop = Constantes.CHUCK_NORIS_TICKS;
			}							
			
			destino = destinoEvitarLoop;
		}
		else
		{
			// nao estamos em loop, podemos fazer qualquer coisa
			destino = bancoMaisProximo();
			
			// se nao conhecemos o banco, vamos procurá-lo
			if (destino == null)
			{
				// Eh hora do berserk?
				if (tick > Constantes.THIS_IS_SPARTAAAAAA)
					return decisao; // this is sparta! - basicamente evita buscar pelo banco, pois jah fizemos mto isso, se preocupe com pegar moedas
				
				bancoConhecido = false;
				destino = desconhecidoMaisProximo();
				
				// se jah conhecemos o mundo inteiro
				if (destino == null)
				{
					// entao nao ha mto o que fazer, vamos embora sem fazer nada
					// esperamos que a arvore tenha mais sucesso
					return decisao;
				}
			}
			
			if (bancoConhecido)
			{
				// se banco eh conhecido mas estamos mto proximos dele, entao deixe que a arvore se encarrege de depositar
				if (Constantes.manhattan(pos, destino) == 1)
					return decisao;
				
				// problemas: ponde ter campers no banco impedindo que a gente deposite
				// podemos ficar perdendo tempo indo ao banco
				// podemos nao conhecer o banco e acabar pegando mtas moedas tentando encontrá-lo
				
				// conhecemos o banco
				// vamos para lá apenas se estamos ricos
				if (numeroMoedas < Constantes.RICO)
				{
					// se nao estamos ricos, deixa pra lá
					return decisao;
				}
			}		
		}
				
		destino = obterVizinhoValido(destino);
		
		if (destino != null)
		{
			// se estamos aqui eh pq conhecemos o destino
			// vamos para o banco se estamos ricos e temos dinheiro para guardar
			decisao.acao = goTo(pos, destino);
		}
		
		return decisao;
	}
	
	/*
	 * Pode alterar a decisao tomada pela árvore
	 */
	private Acao posDecisao(Point pos, Acao decisao)
	{
		// apenas faz algo se árvore nao pôde decidir o que fazer antes		
		if (decisao.acao == Constantes.PARADO)
		{
			Point destino = null;

			// decide o que fazer
			
			// vai para o banco se tiver moedas
			if (sensor.getNumeroDeMoedas() > 0)
				destino = bancoMaisProximo();
			
			// se o banco nao eh conhecido, entao vamos tentar outra coisa 
			if (destino == null)
			{
				// senao conhecemos banco, vamos para algum lugar desconhecido a procura do banco
				destino = desconhecidoMaisProximo();
				
				if (destino == null)
				{
					// se jah conhecemos todo o mapa, entao vamos atrás de moedas deixadas para tras
					destino = moedaMaisProxima();
					
					if (destino == null)
					{
						// nao temos mais o que fazer
						// vamos evitar apenas atrapalhar o outro poupador, ficando longe do banco e longe de corredores
						destino = localErmo();
						
						if (destino == null)
						{
							// se nao existe local ermo, eh melhor ficarmos em movimento do que possivelmente ocupando o meio
							// do caminho
							int max = 50;
							Point alvo = new Point();
							
							while ((destino = obterVizinhoValido(alvo)) == null && max-- > 0)
							{
								alvo.setLocation((int)(Math.random() * (Constantes.MUNDO_TAM - 1)), (int)(Math.random() * (Constantes.MUNDO_TAM - 1)));							
							}
							
							// se tentamos mas nao conseguimos encontrar local, desista
							if (destino == null)
								return decisao;
						}
						else if (destino.equals(pos))
						{
							// se jah estamos no local ermo, entao podemos ficar parados
							destino = null;
						}
							
					}
				}
			}
			else
			{
				// se banco eh conhecido mas estamos mto proximos dele, entao deixe que a arvore se encarrege de depositar
				if (Constantes.manhattan(pos, destino) == 1)
					return decisao;				
			}
			
			if (destino != null)
			{
				decisao.acao = goTo(pos, destino);
				if (decisao.acao == Constantes.PARADO)
				{
					// se nao pudemos andar, entao local era inacessivel e foi colocado na lista de inatingiveis
					// vamos tentar algum outro local
					decisao = posDecisao(pos, decisao);
				}
			}
		}
		
		return decisao;
	}
	
	private Acao decisaoArvore(Point pos, Acao decisao)
	{
		Holder<Double> valorRet;
		double valorParado;
		valorRet = new Holder<Double>(0d);

		// ditancia para ficar onde estamos eh 1 (finge que é pior ficar parado, em questao da fuga de ladroes)
		olharCelula(pos, 1, valorRet);
		
		decisao = avaliarMovimento(pos, Constantes.BUSCA_PROFUNDIDADE, Constantes.PARADO, valorRet, true);
		
		return decisao;
	}
	
	/*
	 * Decide que acao tomar
	 * 
	 */
	private int avaliar(int[] visao, int[] oufato)
	{		
		Point pos;
		Acao decisao;
		pos = getPos();		

		decisao = preDecisao(pos);
		
		// apenas olhamos a árvore se a pre-decisao não fez nada
		if (decisao.acao == Constantes.PARADO)
			decisao = decisaoArvore(pos, decisao);

		decisao = posDecisao(pos, decisao);
		
		return decisao.acao;
	}
	
	public int acao() 
	{
		int[] oufato = sensor.getAmbienteOlfatoPoupador();
		int[] visao = sensor.getVisaoIdentificacao();
		int acao;
		
		descobreMundo();
		acao = avaliar(visao, oufato);
		historicoPosicoes();
		
		return acao;
	}
}